package com.zang.backtrack;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 组合总和IV
 * @author Cizai
 * @since 2022/11/29 18:39
 **/
public class 组合总和IV {

    public int combinationSum4(int[] nums, int target) {

        int[] dp = new int[target + 1];
        dp[0] = 1;

        for (int j = 0; j <= target; j++) {
            for (int i = 0; i < nums.length; i++) {
                // 防止越界
                if (j>=nums[i]) dp[j] += dp[j-nums[i]];
            }
        }
        return dp[target];
    }

}
